#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
int n,m,q,a[N],vis[N],tot;
vector <int> e[N];
void dfs(int u){
	vis[u]=1;a[u]=tot;
	for(int i = 0;i < e[u].size();i++){
		int v=e[u][i];
		if(!vis[v])dfs(v);
	}
}int col[N],cnt,col1[N];
void insert(int x){
	col[x]++;
	if(col[x]==1&&col1[x])cnt--;
}
void del(int x){
	col[x]--;
	if(col[x]==0&&col1[x])cnt++;
}
void insert1(int x){
	col1[x]++;
	if(col[x]==0&&col1[x]==1)cnt++;
}
void del1(int x){
	col1[x]--;
	if(col[x]==0&&col1[x]==0)cnt--;
}
int calc(int l,int r){cnt=0;
	for(int i = 1;i <= tot;i++)col[i]=0,col1[i]=0;
	for(int i = l;i <= r;i++)insert1(a[i]);
	int l1 = l,ans=r-l+1;
	for(int i = l;i <= r;i++){
		insert(a[i]);del1(a[i]);
		while(l1<i){
			del(a[l1]);insert1(a[l1]);
			if(cnt!=0){
				insert(a[l1]),del1(a[l1]);
				break;
			}l1++;
		}
		if(!cnt)ans=min(ans,i-l1+1);
	}return ans;
}
signed main(){
	freopen("destory.in","r",stdin);
	freopen("destory.out","w",stdout);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >> n >> m >> q;
	for(int i = 1,u,v;i <= m;i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i= 1;i <= n;i++)if(!vis[i])tot++,dfs(i);
	for(int i = 1,l,r;i <= q;i++){
		cin >> l >> r;
		cout << calc(l,r) << "\n";
	}
	return 0;
}

